#include <iostream>
#include <vector>
#include <functional>
using namespace std;

function<void(vector<int> &)> output = [](vector<int> &arr) -> void
{
    int length = arr.size();
    for (int i = 0; i < length; ++i)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
};

void shellSort(vector<int> &arr)
{
    int length = arr.size();
    for (int gap = length / 2; gap > 0; gap /= 2)
    {
        for (int i = gap; i < length; ++i)
        {
            for (int j = i; j - gap >= 0 && arr[j] < arr[j - gap]; j -= gap)
            {
                int temp = arr[j - gap];
                arr[j - gap] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

void shellSort_2(vector<int> &arr)
{
    int length = arr.size();
    for (int gap = length / 2; gap > 0; gap /= 2)
    {
        for (int i = gap; i < length; ++i)
        {
            int current = arr[i];
            int j = i - gap;
            for (; j >= 0 && current < arr[j]; j -= gap)
            {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = current;
        }
    }
}

int main()
{
    vector<int> arr = {6, 2, 1, 3, 5, 4, 9, 7, 5, 4, 11, 2, 9, 4, 7, 3, 8, 10};

    vector<int> temp(arr);
    output(temp);
    shellSort(temp);
    output(temp);
    temp = arr;
    output(temp);
    shellSort_2(temp);
    output(temp);
    return 0;
}
